


import org.apache.commons.io.IOUtils;

import java.io.FileInputStream;
import java.io.IOException;
import java.util.*;


public class SliderSolver {
    private static final Move ROOT_MOVE = null;
    private static final StateNode NO_PARENT = null;
    private final Puzzle sourcePuzzle;
    private final Goal targetGoal;
    private final Map<Character, Character> equivalentMapping = new HashMap<Character, Character>();

    public static void main (String[] argv) throws IOException {
        if (argv.length != 2) {
            System.out.println("Error expected two input parameters, a puzzle file and a goal file");
            System.out.println();
            System.out.println("Usage: SliderSolver puzzle-file goal-file");
            return;
        }

        final String puzzleString = IOUtils.toString(new FileInputStream(argv[0]));
        final String goalString   = IOUtils.toString(new FileInputStream(argv[1]));
        final Puzzle puzzle       = new Puzzle(puzzleString);
        final Goal   goal         = new Goal(goalString);

        final SliderSolver solver   = new SliderSolver(puzzle, goal);
        final Solution     solution = solver.solve();
        
        if (solution == null) {
            System.out.println("No solutions found");
            return;
        }
        
        System.out.println(solution);
    }
    
    public SliderSolver(Puzzle puzzle, Goal goal) {
        this.sourcePuzzle = puzzle;
        this.targetGoal = goal;

        this.generateEquivalentMapping();
    }

    private static Shape findEquivalentShape(List<Shape> shapes, Shape targetShape) {
        for (Shape shape : shapes) {
            if (shape.equivalent(targetShape)) {return shape;}
        }

        return null;
    }

    private void generateEquivalentMapping() {
        char  cLetter                  = 'a';
        final List<Shape> puzzleShapes = this.sourcePuzzle.getShapes();
        final List<Shape> goalShapes   = this.targetGoal.getShapes();
        final List<Shape> seenShapes   = new ArrayList<Shape>();

        for (Shape puzzleShape : puzzleShapes) {
            final Shape seenShape = (goalShapes.contains(puzzleShape)) ? null : findEquivalentShape(seenShapes, puzzleShape);

            if (seenShape == null || goalShapes.contains(seenShape)) {
                this.equivalentMapping.put(puzzleShape.getId(), cLetter);
                cLetter += 1;
                seenShapes.add(puzzleShape);
            }
            else {
                this.equivalentMapping.put(puzzleShape.getId(), this.equivalentMapping.get(seenShape.getId()));
            }
        }
    }

    public Solution solve() {
        Queue<StateNode>        nextStates    = new ArrayDeque<StateNode>();
        Set<String>             seenStates    = new HashSet<String>();

        nextStates.offer(new StateNode(new Puzzle(this.sourcePuzzle), ROOT_MOVE, NO_PARENT));

        while (!nextStates.isEmpty()) {
            final StateNode currentState = nextStates.poll();
            final String    puzzleString = this.generateEquivalentPuzzleString(currentState.puzzle);

            if (seenStates.contains(puzzleString)) {
                continue;
            }

            if (this.targetGoal.matches(currentState.puzzle)) {
                return this.buildSolution(currentState);
            }

            seenStates.add(puzzleString);
            this.offerNextStates(nextStates, currentState);
        }

        return null;
    }

    private String generateEquivalentPuzzleString(Puzzle puzzle) {
        return puzzle.createEquivalentStateString(this.equivalentMapping);
    }

    private Solution buildSolution(StateNode currentState) {
        List<StateNode> solutionStates = new ArrayList<StateNode>();

        while(currentState.parentState != null) {
            solutionStates.add(currentState);
            currentState = currentState.parentState;
        }

        Collections.reverse(solutionStates);
        
        final Solution solution = new Solution();

        for (StateNode node : solutionStates) {
            solution.addState(node);
        }
        
        return solution;
    }

    private void offerNextStates(Queue<StateNode> nextStates, StateNode currentState) {
        for (Shape shape : currentState.puzzle.getShapes()) {
            for (Move.Direction direction : findLegalMoves(currentState.puzzle, shape)) {
                final Move move = new Move(shape, direction);

                currentState.puzzle.applyMove(move);
                nextStates.offer(new StateNode(new Puzzle(currentState.puzzle), move, currentState));
                currentState.puzzle.unapplyMove(move);
            }
        }
    }

    private static Set<Move.Direction> findLegalMoves(Puzzle puzzle, Shape shape) {
        final Set<Move.Direction> legalMoves = EnumSet.allOf(Move.Direction.class);

        for (Puzzle.Cell cell : shape.getCells()) {
            final int row = cell.getRow();
            final int col = cell.getCol();

            if (row - 1 < 0 || shapeCanMoveToCell(shape, puzzle.getCell(row - 1, col))) {
                legalMoves.remove(Move.Direction.UP);
            }

            if (col + 1 >= puzzle.getCols() || shapeCanMoveToCell(shape, puzzle.getCell(row, col + 1))) {
                legalMoves.remove(Move.Direction.RIGHT);
            }

            if (row + 1 >= puzzle.getRows() || shapeCanMoveToCell(shape, puzzle.getCell(row + 1, col))) {
                legalMoves.remove(Move.Direction.DOWN);
            }

            if (col - 1 < 0 || shapeCanMoveToCell(shape, puzzle.getCell(row, col - 1))) {
                legalMoves.remove(Move.Direction.LEFT);
            }
        }

        return legalMoves;
    }

    private static boolean shapeCanMoveToCell(Shape shape, Puzzle.Cell cell) {
        return cell.isWall() || !(cell.getShape() == null || shape.equals(cell.getShape()));
    }

    public static class StateNode {
        private final Puzzle puzzle;
        private final Move   move;
        private final StateNode parentState;

        private StateNode(Puzzle puzzle, Move move, StateNode parentState) {
            this.parentState = parentState;
            this.move = move;
            this.puzzle = puzzle;
        }
    }

    public static class Solution {
        final List<Puzzle>     states       = new ArrayList<Puzzle>();
        final List<List<Move>> moveChunks   = new ArrayList<List<Move>>();
        final List<Move>       currentChunk = new ArrayList<Move>();

        Puzzle prevState = null;

        public void addState(StateNode node) {
            if (currentChunk.size() == 0) {
                currentChunk.add(node.move);
            }
            else if (this.currentChunk.get(this.currentChunk.size() - 1).getShape().equals(node.move.getShape())) {
                currentChunk.add(node.move);
            }
            else {
                this.states.add(this.prevState);
                this.moveChunks.add(new ArrayList<Move>(this.currentChunk));
                this.currentChunk.clear();
                currentChunk.add(node.move);
            }

            prevState = node.puzzle;
        }

        private static String moveListToString(List<Move> moves) {
            final StringBuilder sb = new StringBuilder();

            sb.append(moves.get(0).getShape().getId()).append(" ");
            for (Move move : moves) {
                sb.append(move.getDirection()).append(" ");
            }

            return sb.toString();
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder();

            for (int i = 0; i < states.size(); i++) {
                final List<Move> chunk = this.moveChunks.get(i);

                sb.append(moveListToString(chunk)).append(String.format("%n%n")).append(states.get(i)).append(String.format("%n%n"));
            }

            sb.append(moveListToString(this.currentChunk)).append(String.format("%n%n")).append(prevState).append(String.format("%n%n"));

            return sb.toString();
        }
    }
}
